package com.txy.sort;

public class QuickSort {
    // 递归排序
    public static void quick(int []arr, int start, int end) {
        if(start>=end) return;
        int pivot = pivot(arr, start, end);
        quick(arr, start, pivot - 1);
        quick(arr,  pivot + 1, end);
    }
    // 返回基准位置
    private static int pivot(int []arr, int start, int end) {
        int pivot = arr[start];
        int left = start;
        int right = end;
        while(left!=right) {
            while(left < right && arr[right] > pivot)
                right --;
            while(left < right && arr[left] <= pivot)
                left++;
            if(left < right) {
                int t = arr[left];
                arr[left] = arr[right];
                arr[right] = t;
            }
        }
        arr[start]=arr[left];
        arr[left]=pivot;
        return left;
    }

    public static void main(String[] args) {
        int[] arr = new int[] {4,7,3,5,6,2,8,1};
        quick(arr,0, arr.length-1);
        System.out.println(arr);
    }
}
